package com.cn.algorithm02.class07;

import com.cn.algorithm02.class01.CodeUtil;

/***
 * @author: hels
 * @description: 通过数组和完全二叉树自定义堆结构
 **/
public class C02_Heap {
    // 内部静态类
    public static class MyHeap {
        public static int[] heap;
        public static int limit;
        public static int heapSize;

        public MyHeap(int limit) {
            this.limit = limit;
            heap = new int[limit];
            heapSize = 0;
        }

        // push  大根堆结构，每个子树节点的根节点要比叶子节点大
        public static void push(int value)    {
            if (heapSize == limit) {
                throw new RuntimeException("value if full!");
            }

            heap[heapSize] = value;
            // 新增加
            heapInsert(heap, heapSize++);
        }
        private static void heapInsert(int[] heap,  int index) {
            while (heap[index] > heap[(index-1)/2]) {
                CodeUtil.swap(heap, index, (index-1)/2);
                index = (index-1)/2;
            }
        }

        // pop 弹出最大值
        public static int pop() {
            if (heapSize == 0) {
                throw new RuntimeException("myheap is empty!!!");
            }

            int ans = heap[0];
            heap[0] = 0; // 0 代表空
            CodeUtil.swap(heap, 0, --heapSize);
            // 将最大值弹出后，需要对堆进行重新排序
            // 将最后一个值放到第一个位置，然后进行下沉判断
            // 此处堆size已减一
            heapify(heap, 0, heapSize);
            return ans;
        }

        private static void heapify(int[] heap, int index, int heapSize) {
            int left = 2 * index + 1;
            while (left < heapSize) {
                // 找到大的叶子节点
                int larger = left + 1 < heapSize && heap[left+1] > heap[left] ? left+1 : left;
                // 较大叶子节点和根节点比较
                larger = heap[index] >= heap[larger] ? index : larger;
                if (larger == index) {
                    break;
                }

                CodeUtil.swap(heap, index, larger);
                index = larger;
                left = 2 * larger + 1;
            }
        }


    }

    public static void main(String[] args) {
        MyHeap myHeap = new MyHeap(16);
        myHeap.push(9);
        myHeap.push(5);
        myHeap.push(7);
        myHeap.push(4);
        myHeap.push(3);
        myHeap.push(7);
        myHeap.push(6);
        myHeap.push(3);
        myHeap.push(3);
        myHeap.push(2);
        myHeap.push(6);
        myHeap.push(10);

        CodeUtil.printArray(myHeap.heap);
        System.out.println(myHeap.pop());
        System.out.println(myHeap.pop());
        CodeUtil.printArray(myHeap.heap);


    }
}
